package cn.edu.ncepu;

import java.math.BigInteger;

public class ModularInverseBigInteger {

    // 最大公约数（BigInteger版）
    public static BigInteger gcd(BigInteger m, BigInteger n) {
        if (m.compareTo(n) < 0) {
            return gcd(n, m);
        }
        while (!m.mod(n).equals(BigInteger.ZERO)) {
            BigInteger temp = m;
            m = n;
            n = temp.mod(n);
        }
        return n;
    }

    // 二进制快速幂（BigInteger版）
    public static BigInteger binaryExponentiation(BigInteger base, BigInteger power) {
        BigInteger power2 = BigInteger.ONE;
        BigInteger r = BigInteger.ONE;
        BigInteger p = base;
        while (power2.compareTo(power) <= 0) {
            if (power2.and(power).compareTo(BigInteger.ZERO) != 0) {
                r = r.multiply(p);
            }
            p = p.multiply(p);
            power2 = power2.shiftLeft(1);
        }
        return r;
    }

    // 欧拉函数（BigInteger版，n需为正整数且不超过Integer.MAX_VALUE）
    public static BigInteger eulerTotient(BigInteger n) {
        if (n.compareTo(BigInteger.ZERO) < 0) {
            throw new IllegalArgumentException("n必须为非负整数");
        }
        int nInt = n.intValue();
        BigInteger[] phi = new BigInteger[nInt + 1];
        for (int i = 0; i <= nInt; i++) {
            phi[i] = BigInteger.valueOf(i);
        }
        for (int i = 1; i <= nInt; i++) {
            for (int j = i << 1; j <= nInt; j += i) {
                phi[j] = phi[j].subtract(phi[i]);
            }
        }
        return phi[nInt];
    }

    // 模逆元（BigInteger版）
    public static BigInteger modularInverse(BigInteger a, BigInteger m) {
        if (!gcd(a, m).equals(BigInteger.ONE)) {
            throw new IllegalArgumentException(a + "," + m + "不互质，没有模乘逆元");
        }
        BigInteger phiM = eulerTotient(m);
        BigInteger result = binaryExponentiation(a, phiM.subtract(BigInteger.ONE)).mod(m);
        return result.compareTo(BigInteger.ZERO) < 0 ? result.add(m) : result;
    }

    public static void main(String[] args) {
        // 测试用例1：a=3, m=2
        BigInteger a1 = BigInteger.valueOf(3);
        BigInteger m1 = BigInteger.valueOf(2);
        try {
            BigInteger x1 = modularInverse(a1, m1);
            System.out.printf("%s * %s %% %s = %s%n", a1, x1, m1, a1.multiply(x1).mod(m1));
        } catch (IllegalArgumentException e) {
            System.err.println(e.getMessage());
        }

        // 测试用例2：a=1024, m=997
        BigInteger a2 = BigInteger.valueOf(1024);
        BigInteger m2 = BigInteger.valueOf(997);
        try {
            BigInteger x2 = modularInverse(a2, m2);
            System.out.printf("%s * %s %% %s = %s%n", a2, x2, m2, a2.multiply(x2).mod(m2));
        } catch (IllegalArgumentException e) {
            System.err.println(e.getMessage());
        }

        // 测试用例3：a=3, m=6
        BigInteger a3 = BigInteger.valueOf(3);
        BigInteger m3 = BigInteger.valueOf(6);
        try {
            BigInteger x3 = modularInverse(a3, m3);
            System.out.println(x3);
        } catch (IllegalArgumentException e) {
            System.err.println(e.getMessage());
        }
    }
}